/**
例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

就是对二叉树【先序】遍历，根 -》左 -》右
*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution
{
public:
    void flatten(TreeNode *root)
    {
        if (root == NULL)
            return;

        // 从 root 节点开始循环
        while (root != NULL) // 假设 root = 1
        {
            // 只处理具有【左孩子】的节点
            if (root->left)
            {
                /**
                         1
                        / \
                       2   5
                      / \   \
                     3   4   6

                     1. 取出 root【左孩子】节点
                     2. 解决 4->5: 继续找到【左孩子】下方【最右】的【子孙节点】
                        2.1【最右】的【子孙节点】->right = root->right
                     3. 解决 1->2: root->right = root->left
                     4. 解决 1->NULL: root->left = NULL
                 */


                // 取出【左】子节点
                TreeNode *tp = root->left; // 假设 tp = 2

                // 走到【左孩子】【最下方】的【右】子节点
                while (tp->right != NULL) // 最终 tp = 4
                    tp = tp->right;

                // 4 right-> 5
                tp->right = root->right;

                // 1 right-> 2
                root->right = root->left;

                // 清空 1 left->
                root->left = NULL;
            }

            // 不存在【左孩子】的节点，访问他的【右子树】
            root = root->right;
        }
    }
};
